package linkList;

/**
 * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * <p>
 * 题目数据 保证 整个链式结构中不存在环。
 * <p>
 * 注意，函数返回结果后，链表必须 保持其原始结构 。
 */
public class O0207_getIntersectionNode {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        int lenA = 0;
        int lenB = 0;
        // 计算两个链表的长度
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        while (curB != null) {
            lenB++;
            curB = curB.next;
        }

        curA = headA;
        curB = headB;
        // 确保A是长的那一条，如果不是则交换两条链表
        if (lenA < lenB) {
            int tempLen = lenA;
            lenA = lenB;
            lenB = tempLen;
            ListNode tempNode = curA;
            curA = curB;
            curB = tempNode;
        }

        int n = lenA - lenB;
        for (int i = 0; i < n; i++) {
            curA = curA.next;
        }

        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }

        return null;
    }

    public static void main(String[] args) {
        O0207_getIntersectionNode solution = new O0207_getIntersectionNode();
//        solution.getIntersectionNode();
    }
}
